package sort;

/**
 * 归并排序 O(nlogn)
 *     1.先将原数组不断拆分，直到每个子数组中只有一个元素为止，第一阶段归而为1结束。
 *     2.并：将相邻的两个数组合并为有序的数组，重复此操作，直到整个数组全部有序。
 */
public class MergeSort {

    /** 归并排序：递归 **/
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr, 0, arr.length - 1);
    }
    // "归" 操作
    private static void mergeSortInternal(int[] arr, int l, int r) {
        //边界条件
        if(l >= r){
            //说明子数组只剩一个元素，归结束
            return;
        }
        /**
         * 优化2：数据量为千万级别时才适用
         * 没有必要将子数组一直分割到只剩下一个元素，其实当子数组元素个数<=15时，直接用插入排序效率就很高
         */
//        if(r - l + 1 <= 15){
//            //小区间内直接使用插入排序
//            insertionSort(arr, l, r);
//            return;
//        }
        //从中间一分为二
        int mid = l + (r - l) / 2;
        //递归去分解两个子数组
        mergeSortInternal(arr, l, mid);
        mergeSortInternal(arr, mid + 1, r);
        //此时，"归"结束，开始"并"操作
        /**
         * 优化1：
         * 如果[l, r]的元素整体有序(arr[mid] <= arr[mid + 1])，就不需要进行merge操作了
         */
        if(arr[mid] > arr[mid + 1]){
            merge(arr, l, mid, r);
        }
    }
    // “并” 操作,将[l, r] 的元素进行排序
    private static void merge(int[] arr, int l, int mid, int r) {
        //先创建一个临时数组，用于存储[l, r]的元素
        int[] temp = new int[r - l + 1];
        for(int i = 0; i < temp.length; i++){
            temp[i] = arr[l + i];
        }
        //此时需要明白[l, mid]和[mid+1, r]这两个子数组本身就是有序的
        //在这种情况下，做整体排序的话，就同时遍历两条子数组，把值小的元素放在前面
        //注意：遍历的是temp数组，真正改动的是arr[]
        // i1和i2表示两条子数组的起始坐标
        int i1 = 0, i2 = mid - l + 1;
        for(int k = l; k <= r; k++){
            if(i1 == mid - l + 1){
                //此时i1越界，直接添加i2
                arr[k] = temp[i2];
                i2 ++;
            }else if(i2 == r - l + 1){
                //此时i2越界，直接添加i1
                arr[k] = temp[i1];
                i1 ++;
            }else if(temp[i1] <= temp[i2]){ //保证排序的稳定性
                arr[k] = temp[i1];
                i1 ++;
            }else{
                arr[k] = temp[i2];
                i2 ++;
            }
        }
    }
    //插入排序法: 区间内[l, r]
    private static void insertionSort(int[] arr, int l, int r) {
        // i表示无序区间的首元素
        for(int i = l + 1; i <= r; i++){
            for(int j = i; j - 1 >= l && arr[j] < arr[j-1]; j--){
                arr[j] = arr[j] + arr[j-1] - (arr[j-1] = arr[j]);
            }
        }
    }

    /** 归并排序：迭代 **/
    public static void mergeSortNonRecursion(int[] arr) {
        // sz表示每次合的子数组的长度
        for(int sz = 1; sz < arr.length; sz += sz){
            //内层的i表示每次合并的两条子数组的开始索引
            //i + sz 表示右数组的开始索引
            for(int i = 0; i + sz < arr.length; i += sz + sz){
                //防止右区间的边界越界
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, arr.length - 1));
            }
        }
    }
}
